package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:合并区间
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 *
 * 示例 1：
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 * 示例2：
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 * 提示：
 * 1 <= intervals.length <= 104
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 104
 *
 *
 * author: Mr.Du
 * Date: 2022/11/16
 * Time: 23:36
 */
public class Merge {
    
    public int[][] merge(int[][] nums) {
        Map<Integer,Integer> mp = new TreeMap<>();
        // 去重，key相同的，value小的不加map
        for(int i = 0;i < nums.length;i++){
            if(mp.containsKey(nums[i][0])){
                if(mp.get(nums[i][0]) < nums[i][1])
                    mp.put(nums[i][0],nums[i][1]);
            }else{
                mp.put(nums[i][0],nums[i][1]);
            }
        }
        
        Map<Integer,Integer> mp1 = new TreeMap<>();
        // 用来记录区间的左右边界
        int l = -1;
        int r = -1;
        for(Map.Entry<Integer,Integer> e : mp.entrySet()){
            int key = e.getKey();
            int value = e.getValue();
            //第一次添加
            if(l == -1){
                mp1.put(key,value);
                l = key;
                r = value;
            }else{
                // 这次的添加key，比上次value大，那么说明该区间起始位置不在上个区间里面，直接添加
                if(key > r){
                    mp1.put(key,value);
                    // 更新左右边界
                    l = key;
                    r = value;
                }else{
                    // 这次添加的区间起始位置在上次添加区间，末位置如果大于上次添加区间的末位置，
                    // 则更新上次添加区间末位置，否则该区间在上个添加区间里面，不做操作
                    if(value > r ){
                        mp1.put(l,value);
                        // 更新右边界
                        r = value;
                    }
                }
            }
        }
        int[][] arr = new int[mp1.size()][2];
        int i = 0;
        // 赋值操作
        for(Map.Entry<Integer,Integer> e : mp1.entrySet()){
            arr[i][0] = e.getKey();
            arr[i++][1] = e.getValue();
        }
        return arr;
    }

    /**
     * 真骚，这个方法
     * 合并区间数组。
     * 给定一个区间数组，每个区间由两个整数表示，分别是区间的开始和结束位置。
     * 将这些区间合并，并返回合并后的区间数组。
     *
     * @param intervals 区间数组，每个区间由长度为2的整数数组表示。
     * @return 合并后的区间数组。
     */
    public int[][] merge1(int[][] intervals) {
        BitSet bitSet = new BitSet();
        int max = 0;
        // 遍历每个区间，将其开始和结束位置转换为BitSet中的位，并标记为true
        for (int[] interval : intervals) {
            int temp = interval[1] * 2 + 1;
            bitSet.set(interval[0] * 2, temp, true);
            max = temp >= max ? temp : max; // 更新最大值
        }

        int index = 0, count = 0;
        // 遍历BitSet，重新构建合并后的区间数组
        while (index < max) {
            int start = bitSet.nextSetBit(index);
            int end = bitSet.nextClearBit(start);

            int[] item = {start / 2, (end - 1) / 2}; // 计算合并后的区间开始和结束位置
            intervals[count++] = item;

            index = end;
        }
        // 创建新的区间数组，将合并后的区间复制到新数组中
        int[][] ret = new int[count][2];
        for (int i = 0; i < count; i++) {
            ret[i] = intervals[i];
        }
        return ret;
    }

    /**
     * 合并区间数组。
     * 给定一个区间数组，其中每个区间都由两个正整数边界构成，使得第一个边界的值始终小于等于第二个边界的值。
     * 将区间数组合并成一个结果区间数组，使得所有的区间不重叠，并且按照区间起始边界从小到大排序。
     *
     * @param intervals 区间数组，每个区间由两个正整数边界构成。
     * @return 合并后的区间数组，按照起始边界从小到大排序，且不重叠。
     */
    public int[][] merge2(int[][] intervals) {
        int m = intervals.length; // 区间数组的长度
        LinkedList<int[]> list = new LinkedList<>(); // 用于存储合并后的区间的链表
        // 对区间数组按照起始边界进行升序排序
        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0];
        });
        list.add(intervals[0]); // 将排序后的第一个区间添加到链表中
        for(int i = 1; i < m; i++){
            int[] cur = intervals[i]; // 当前遍历的区间
            int[] last = list.getLast(); // 链表中最后一个区间
            // 如果当前区间的起始边界小于等于链表中最后一个区间的结束边界，则进行合并
            if (cur[0] <= last[1]) {
                // 引用的nb之处
                last[1] = Math.max(last[1], cur[1]); // 合并区间
            } else {
                list.add(cur); // 否则，将当前区间直接添加到链表末尾
            }
        }
        // 将链表转换成二维数组并返回
        return list.toArray(new int[0][0]);
    }

    public static void main(String[] args) {
        int[][] nums = {{1,8},{2,6}};
        System.out.println(new Merge().merge1(nums));
    }
}
